/**********************************************************

@description:use double loop linklist
*File Name:binary_tree_level.c
*Author: ydx
*mail: yudongxiang93@163.com
*Create Time: Sat 26 Apr 2025 10:41:23 AM CST
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
typedef struct tnode{
	char data;
	struct tnode* lchild;
	struct tnode* rchild;
}tnode;
typedef struct qnode{
	void * data;
	struct qnode* pre;
	struct qnode* next;
}qnode;
qnode *initq(){
	qnode *q=(qnode*)malloc(sizeof(qnode));
	q->data=NULL;
	q->pre=q;
	q->next=q;
	return q;
}
/*tail insert*/
void enqueue(qnode* q,void * data){
	if(!data)
		return;
	qnode *n=(qnode*)malloc(sizeof(qnode));
	n->data=data;
	n->pre=q->pre;
	n->next=q;
	q->pre->next=n;
	q->pre=n;
}
int isEmpty(qnode* q){
	int ret=0;
	if(q==q->next){
		ret=1;	
	}
	return ret;
}
qnode* dequeue(qnode* q){
	if(isEmpty(q)){
		return NULL;
	}else{
		qnode* n=q->next;
		q->next->next->pre=q;
		q->next=q->next->next;
		return n;
	}

}
typedef void (*visit)(tnode*);
void pn(tnode* n){
	if(n)
		printf("%c ",n->data);
}

void leveltraverse(tnode *t,qnode *q,visit v){
	enqueue(q,t);
	while(!isEmpty(q)){
		qnode *n=dequeue(q);
		if(n){
			tnode *tmp=(tnode*)(n->data);
			v(tmp);
			if(tmp){
				enqueue(q,tmp->lchild);
				enqueue(q,tmp->rchild);
			}
		}
	}
}

void createTree1(tnode **n,char*data,int* idx){
	char ch;
	ch=data[*idx];
	*idx+=1;
	if(ch == '#'){
		*n=NULL;		
	}else{
		*n=(tnode*)malloc(sizeof(tnode));
		(*n)->data=ch;
		createTree1(&(*n)->lchild,data,idx);
		createTree1(&(*n)->rchild,data,idx);
	}
}
void preorder(tnode* t,visit v){
	v(t);
	if(t){
		preorder(t->lchild,v);
		preorder(t->rchild,v);
	}
}
void destroy(qnode* q){
	qnode *n=q;
	while(q){
		n=q->next;	
		if(n==q){
			free(q);
			return;
		}
		free(q);
		q=n;
	}
}
int main(int argc,char ** argv){
	tnode *t=NULL;
	int index=0;
	qnode *q=initq();
	createTree1(&t,argv[1],&index);
	leveltraverse(t,q,pn);
	//preorder(t,pn);
	printf("\n");
	destroy(q);	
}
